【题解】 [POI2007]ZAP-Queries 莫比乌斯反演 luogu3455

很显然是让我们求出下式：

$ans=\sum_{i=1}^{A}\sum_{j=1}^{B}[gcd(i,j)=K]$

根据性质可以得到：

$ans=\sum_{i=1}^{\lfloor\frac{A}{K}\rfloor}\sum_{j=1}^{\lfloor\frac{B}{K}\rfloor}[gcd(i,j)=1]$

我们设两个函数：

函数 $f$，$f(x)$ 表示 $\sum_{i=1}^{\lfloor\frac{A}{K}\rfloor}\sum_{j=1}^{\lfloor\frac{B}{K}\rfloor}[gcd(i,j)=x]$
函数 $g$ ，$g(x)$ 表示 $\sum_{i=1}^{\lfloor\frac{A}{K}\rfloor}\sum_{j=1}^{\lfloor\frac{B}{K}\rfloor}[x|gcd(i,j)]$

我们可以得到：

$g(x)=\sum_{x|d} f(x)$

这是莫比乌斯反演的第二个形式：

$g(n)=\sum_{n|d} f(n) \ \Rightarrow \ f(n)=\sum_{n|d}g(d) \cdot \mu(\frac{d}{n})$

于是：

$g(x)=\sum_{x|d} f(x) \ \Rightarrow \ f(x)=\sum_{x|d}g(x) \cdot \mu(\frac{d}{x})$ $=g(x)=\sum_{x|d} f(x) \ \Rightarrow \ f(x)=\sum_{x|d}g(\frac{d}{x}) \cdot \mu(x)$

设 $n=\lfloor\frac{A}{K}\rfloor\ ,\ m=\lfloor\frac{B}{K}\rfloor$

那么：

$g(x)=\sum_{i=1}^{n}\sum_{i=1}^{m} [x|gcd(i,j)]=\sum_{i=1}^{\lfloor\frac{n}{K}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{K}\rfloor}[1|gcd(i,j)]$ $=\sum_{i=1}^{\lfloor\frac{n}{K}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{K}\rfloor}[1|gcd(i,j)]=\lfloor\frac{A}{K}\rfloor \times\lfloor\frac{B}{K}\rfloor$ $ans=f(1)$ $f(1)=\sum_{i=1}^{n}\mu(i)*g(i)=\sum_{i=1}^{n}\mu(i)*\lfloor\frac{A}{K}\rfloor *\lfloor\frac{B}{K}\rfloor$

这个式子是 $O(n)$ 的。

发现 $\lfloor\frac{A}{K}\rfloor \times\lfloor\frac{B}{K}\rfloor$ 可以整除分块，于是我们便可以做到 $O(\sqrt{x})$

Code：

#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>

const int N=1e5+2;
const int inf=1e9+9;

int T,cnt;
int prime[N],mui[N],vis[N];
long long sum[N];

inline int _Pre_mui(){
    mui[1]=1;
    for(int i=2;i<=N;++i){
        if(!vis[i])prime[++cnt]=i,mui[i]=-1;
        for(int j=1;j<=cnt;++j){
            if(i*prime[j]>=N)break;
            vis[i*prime[j]]=1;
            if(!(i%prime[j])){mui[i*prime[j]]=0;break;}
            else mui[i*prime[j]]=-mui[i];
        }
    }for(int i=1;i<=N;++i)sum[i]=sum[i-1]+mui[i];
    return 0;
}

#define min(x,y) ((x)<(y)?(x):(y))

inline void solve(int n,int m,int k){
    long long ans=0;
    n/=k,m/=k;
    int lim=min(n,m);
    for(int i=1;i<=lim;){
        long long j=min(n/(n/i),m/(m/i));
        ans+=1ll*(sum[j]-sum[i-1])*(n/i)*(m/i);
        i=j+1;
    }printf("%lld\n",ans);
    return;
}

int main(){
    _Pre_mui();
    scanf("%d",&T);
    while(T--){
        int n,m,k;
        scanf("%d%d%d",&n,&m,&k);
        solve(n,m,k);
    }return 0;	
}

所以就没了。

本文标题:【题解】 [POI2007]ZAP-Queries 莫比乌斯反演 luogu3455

文章作者:Qiuly

发布时间:2019年02月27日 - 00:00

最后更新:2019年03月29日 - 13:54

原始链接:http://qiulyblog.github.io/2019/02/27/[题解]luoguP3455/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际转载请保留原文链接及作者。